Laboratorio 1: Semplici algoritmi numerici

In questo laboratorio vi viene richiesto di scrivere alcuni semplici algoritmi numerici, in modo da dimostrare di avere imparato i comandi principali di Python. Gli esercizi sono basati sul capitolo 3 del testo di riferimento.

Esercizio 1: Radice cubica di un numero intero ed Enumerazione Esaustiva

Il primo esercizio vi chiede di scrivere una funzione chiamata RadiceCubica che prende in input un numero intero e restituisce una coppia di valori (messagge,result), in cui:

message è una stringa che descrive il risultato dell'operazione, e può assumere i due valori ok oppure failed.
result è pari ad una stringa vuota se message è failed, oppure è il risultato della radice cubica se message è pari a ok.

Si completi quindi la seguente funzioni e si controlla il suo corretto funzionamento con i seguenti input:

27
-8
57893
1957816251
7406961012236344616
35.7
'ciao'

Per svolgere questo esercizio potrebbe essere utile usare la funzione abs(x). Per sapere come usare questa funzione avvalersi dell'help di Python con il comando help(abs).



In [ ]:

    
# COMPLETARE LA FUNZIONE SEGUENTE
def RadiceCubica(x):
    # DA COMPLETARE
    # DA COMPLETARE
    # DA COMPLETARE
 
    # Se non si trova la radice cubica:
    return "failed", ""
    
# Funzione di test per la funzione che dovete implementare
def UnitTest():
    Xs = [27, -8, 57893, 1957816251, 7406961012236344616, 35.7, 'ciao']
    for i,x in enumerate(Xs):
        msg, y = RadiceCubica(x)
        if msg == 'ok':
            print("Test ",i+1,' ok, result: ', y)
        else:
            print("Test ",i+1,' failed!')
            
# Esegui il test
UnitTest()

Esercizio 2: Radice quadrata di un numero reale non negativo

Il secondo esercizio vi chiede di scrivere una funzione chiamata ApxRadiceQuadrata(x) che calcoli la radice quadrata di un qualsiasi numero reale non negativo x. La radice quadratata del numero dato in input non deve essere esatta, ma deve essere approssimata con un fattore espilon che viene passata in input alla funzione. In pratica si chiede di implementare la funzione:

$$f : \mathbb{R} \rightarrow \mathbb{R} \quad \quad y = f(x)$$

tale che:

$$\mid y-\sqrt{x} \mid \leq \epsilon$$

Si assuma come valore di default il numero $\epsilon = 10^{-2}$. Si test il programma con i numeri 25, 0.25, 123456, e 123456789.



In [ ]:

    
# COMPLETARE LA FUNZIONE SEGUENTE
def ApxRadiceQuadrata(x, epsilon=1e-02):
    # DA COMPLETARE
    # DA COMPLETARE
    # DA COMPLETARE    
    return "failed", "", 0
    
# Funzione di test per la funzione che dovete implementare
def UnitTest():
    Xs = [25, 0.25, 123456]
    for i,x in enumerate(Xs):
        msg, y, iter = ApxRadiceQuadrata(x)
        if msg == 'ok':
            print("Test ",i+1,' ok, result: ', y, ' | iterations:', iter)
        else:
            print("Test ",i+1,' failed! | iterations:', iter)
                  
# Potete scegliere tra
UnitTest()
# Oppure, chiamare la funzione con un parametro alla volta
#print(ApxRadiceQuadrata(0.25))

Esercizio 3: Bisection Search

Si implementi ora una funzione che calcoli, come nell'esercizio precedente, un valore approsimato della radice quadrata di un numero dato, ma che trovi tale valore con un numero ridotto di iterazioni.

Suggerimento: L'algoritmo dovrebbe usare lo stesso metodo che usiamo per cercare un vocabolo in un dizionario: ad ogni iterazione dovremmo dividere lo spazio di ricerca in due metà e decidere in quale delle due continuare a cercare. Lo spazio di ricerca iniziale dovrebbe essere $[0..x]$ se $x>1$, oppure $[0..1]$ se $x \leq1 $.



In [ ]:

    
# COMPLETARE LA FUNZIONE SEGUENTE
def BS_ApxRadiceQuadrata(x, epsilon=1e-02):
    # DA COMPLETARE
    # DA COMPLETARE
    # DA COMPLETARE
    return "failed", "", 0
    
# Funzione di test per la funzione che dovete implementare
def UnitTest():
    Xs = [25, 0.25, 123456, 123456789]
    for i,x in enumerate(Xs):
        print('----------- Start Test ', i+1, ' -------------')
        msg, y, iter = BS_ApxRadiceQuadrata(x)
        if msg == 'ok':
            print('TEST ',i+1,' ok, result: ', y, ' | iterations:', iter)
        else:
            print('TEST ',i+1,' failed! | iterations:', iter)
        print('----------- Test ', i+1, ' Completed -------------')
                  
# Potete scegliere tra
UnitTest()

Il Metodo di Newton Raphson

Un degli esempi più noti di algoritmi approssimati viene attribuito a Isaac Newton e Joseph Raphson, che avrebbero scoperto lo stesso metodo allo stesso tempo, ma senza aver lavorato insieme.

Il metodo può essere usato per trovare le radici di molte funzioni, ma in questo esercizio ci limitiamo alle radici di polinomi con una sola variabile.

Un polinomio è o 0 oppure una somma finita di termini non nulli. Ogni termine non nullo è composto di una costante, il suo coefficiente, che viene moltiplicato per una variabile che viene elevata ad un esponente intero non negativo; il valore dell'esponente è chiamato il grado del termine. Il grado di un polinomio è pari al massimo dei gradi dei suoi termini. Per esempio, il polinomio: $$3x^2 + 2x +3$$ ha grado pari a due.

Sia ora $p(x)$ un polinomio e $\bar{x}$ un numero reale: indichiamo con $p(\bar{x})$ il valore che il polinomio assume in $\bar{x}$. La radice di un polinomio è una soluzione dell'equazione $p(x) = 0$, ovvero la radice è un numero reale $\bar{x}$ tale per cui $p(\bar{x}) = 0$. Per esempio, il problema di trovare un'approssimazione della radice quadrata di 24 può essere scritto come il problema di trovare le radici del polinomio $x^2 - 24 \approx 0$.

Newton ha dimostrato un teorema che implica che se un numero $\bar{x}$ è una approssimazione di una radice di un polinomio, allora $\bar{x} - \frac{p(\bar{x})}{p'(\bar{x})}$, in cui $p'(x)$ è la derivata prima di $p(x)$, è una approsimazione migliore di tale radice. In pratica, il metodo di Newton Raphson continua ad iterare tra approssimazioni successive sino a quando non trova una radice del polinimio che ha la precisione desiderata.

Esercizio 4: Implementare Newton Raphson

In questo esercizio vi viene chiesto di implementare una funzione che prende in input:

Una funzione che calcola il valore di un dato polinomio $p(x)$. Per esempio, una funzione che calcola: $p(x) = cx^2 + 123456789$ con $c=1$ e $k=-123456789$.
Una seconda funzione che calcola il valore della derivata prima del polinomio $p(x)$, che chiamiamo per semplicità $q(x)$. Dall'esempio precedente, avremmo $q(x) = 2cx$.
La tolleranza desiderata $\epsilon$, con valore di default $\epsilon = 10^{-2}$.

Vi viene chiesto di implementare la funzione chiamata NewtonRaphson(p, q, espilon) che calcola le approssimazioni successive della radice del polinomio, sino ad ottenere una radice delle precisione richiesta. L'output della funzione sarà come quello richiesto nell'esercizio 3.



In [ ]:

    
# Polinomio di cui trovare la radice
#def p(x):
    # DA COMPLETARE

# Derivata prima del polinomio dato
#def q(x):
    # DA COMPLETARE



In [ ]:

    
def NewtonRaphson(p, q, epsilon=1e-02):
    # DA COMPLETARE
    # DA COMPLETARE
    # DA COMPLETARE
 
    return 'failed', '', 0



In [ ]:

    
# Test della funzione implementata
NewtonRaphson(p,q)



In [ ]: